package com.google.codejam.qua2013.treasure;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

public class Treasure {

    public static Integer[]                keyConsumers        = new Integer[401];
    public static Integer[]                keyInPackage        = new Integer[401];
    public static Integer[][]              chestContainsKey    = new Integer[201][401];
    public static Integer[]                allSupplyKeys       = new Integer[401];
    public static HashMap<String, Boolean> Status              = new HashMap<String, Boolean>();
    public static int                      chestIsOpenedNumber = 0;

    public static void main(String[] args) {
        String inputFile = args[0];
        String outputFile = args[1];
        readAndSolve(inputFile, outputFile);
    }

    public static String readAndSolve(String inFileName, String outFileName) {
        File file = new File(inFileName);
        BufferedReader bufferedReader = null;
        try {
            bufferedReader = new BufferedReader(new FileReader(file));
            FileWriter fileWriter = new FileWriter(outFileName, true);
            String readLine = null;
            int testCase = 0;
            int currentTestCaseIndex = 1;
            int line = 0;
            int initialKeyNumber = 0;
            int chestNumber = 0;
            int keysYouHave = 0;

            ArrayList<Chest> chests = new ArrayList<Chest>();

            while ((readLine = bufferedReader.readLine()) != null) {

                if (readLine.trim().length() <= 0) {
                    continue;
                }
                if (line == 0) {
                    testCase = Integer.parseInt(readLine);
                    resetArray(keyConsumers);
                    resetArray(keyInPackage);
                    resetArray(allSupplyKeys);
                    reset2DArray(chestContainsKey);
                    Status.clear();
                    line++;
                    continue;
                }
                if (initialKeyNumber == 0 && chestNumber == 0) {
                    // begin to read keynumber and chest number
                    String[] keyNumberChestNumber = readLine.split(" ");
                    initialKeyNumber = Integer.parseInt(keyNumberChestNumber[0]);
                    chestNumber = Integer.parseInt(keyNumberChestNumber[1]);
//                     System.out.println(currentTestCaseIndex + "--------------------------:");
//                     System.out.println(readLine);
                    continue;
                }
//                 System.out.println(readLine);
                if (initialKeyNumber > 0) {
                    String[] keys = readLine.split(" ");
                    for (int i = 0; i < keys.length; i++) {
                        keyInPackage[Integer.valueOf(keys[i])]++;
                        allSupplyKeys[Integer.valueOf(keys[i])]++;
                    }
                    keysYouHave += keys.length;
                    initialKeyNumber = 0;
                    continue;
                }
                if (chestNumber > 0) {
                    Chest chest = new Chest();
                    String[] chestStatus = readLine.split(" ");
                    chest.entryKey = chestStatus[0];
                    chest.index = chests.size();
                    int containsKeyNumber = Integer.parseInt(chestStatus[1]);
                    for (int i = 0; i < containsKeyNumber; i++) {
                        chest.containKeys.add(chestStatus[2 + i]);
                        chestContainsKey[chest.index][Integer.valueOf(chestStatus[2 + i])]++;
                        allSupplyKeys[Integer.valueOf(chestStatus[2 + i])]++;
                    }

                    keyConsumers[Integer.valueOf(chest.entryKey)]++;
                    chests.add(chest);
                    // addEntryKeyChestMap(entryKeyChestMap, chestStatus[0], chest);
                    chestNumber--;
                }
                if (chestNumber == 0) {
                    // begin to handle input
                    // ArrayList<String> test = new ArrayList<String>();
                    // for(int i=0; i<10; i++){
                    // test.add("abc");
                    // }
                    // for(int i=0; i<10; i++){
                    // test.add("abcd");
                    // }
                    // ArrayList<String> test2 = new ArrayList<String>();
                    // for(int i=0; i<5; i++){
                    // test2.add("abc");
                    // }
                    // System.out.println(test);
                    // removeElements(test, test2);
                    // test.addAll(test2);
                    // System.out.println(test);
                    // System.out.println("Doing Case #" + currentTestCaseIndex);
                    fileWriter.append("Case #" + currentTestCaseIndex + ":");
                    ArrayList<String> openPath = new ArrayList<String>();
                    if (!isImpossible()) {
                        fileWriter.append(" IMPOSSIBLE");
                    } else if (solve(keysYouHave, chests, openPath)) {
                        for (int i = 0; i < openPath.size(); i++) {
                            fileWriter.append(" " + openPath.get(i));
                        }
                    } else {
                        fileWriter.append(" IMPOSSIBLE");
                    }
                    chests.clear();
                    keysYouHave = 0;
                    resetArray(keyConsumers);
                    resetArray(keyInPackage);
                    resetArray(allSupplyKeys);
                    reset2DArray(chestContainsKey);
                    Status.clear();
                    chestIsOpenedNumber = 0;

                    fileWriter.append("\n");
                    fileWriter.flush();
                    // mark status
                    if (currentTestCaseIndex == testCase) {
                        break;
                    }
                    currentTestCaseIndex++;
                }

            }
            fileWriter.flush();
            fileWriter.close();
            bufferedReader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    public static void resetArray(Integer[] array) {
        for (int j = 0; j < 401; j++) {
            array[j] = 0;
        }
    }

    public static void reset2DArray(Integer[][] array) {
        for (int i = 0; i < 201; i++) {
            for (int j = 0; j < 401; j++) {
                array[i][j] = 0;
            }
        }
    }

    public static boolean solve(int keysYouHave, ArrayList<Chest> chests, ArrayList<String> resultPath) {
        if (keysYouHave == 0 && !haveBeenAllOpened(chests)) {
            return false;
        }
        for (int i = 0; i < chests.size(); i++) {
            Chest chest = chests.get(i);
            if (chest.isOpen || keyInPackage[Integer.valueOf(chest.entryKey)] <= 0) {
                // can't open or no need
                // System.out.println("can't open or no need:"+chest.index);
                continue;
            }

            ArrayList<String> tmp = (ArrayList<String>) resultPath.clone();
            String chestIndex = String.valueOf(chest.index + 1);
            tmp.add(chestIndex);
            sortByLengthAsc(tmp);
            String statusKey = tmp.toString();
            // System.out.println(statusKey);
            if (Status.containsKey(statusKey) && Status.get(statusKey) == false) {
                // System.out.println("false key:"+statusKey);
                continue;
            }

            // if this will lead to no result, skip it as soon as possible
            // if (!preCheck(chest) && chest.containKeys.size()<=0) {
            // System.out.println("precheck fail:"+chest.index);
            // continue;
            // }
            // System.out.println("open chest:" + chest.index);
            chest.isOpen = true;
            chestIsOpenedNumber++;
            keysYouHave--;// the key is used
            keyInPackage[Integer.valueOf(chest.entryKey)]--;

            keysYouHave += chest.containKeys.size();// you have more keys
            for (int j = 0; j < chest.containKeys.size(); j++) {
                keyInPackage[Integer.valueOf(chest.containKeys.get(j))]++;
            }

            resultPath.add(chestIndex);
            // if(chest.index==19){
            // System.out.println("open chest:" + chest);
            // System.out.println("keys you have:" + keysYouHave);
            // System.out.println("chests status:" + chests);
            // System.out.println("Result path:" + resultPath);
            // System.out.println("keyConsumers:"+keyConsumers);
            // System.out.println("keyInPackage:"+keyInPackage);
            // System.out.println("chestIsOpenedNumber:"+chestIsOpenedNumber);
            // System.out.println("chestIsOpenedNumber:"+chestContainsKey);
            //
            // }
            boolean isSolved = solve(keysYouHave, chests, resultPath);
            // if(chest.index==19){
            // System.out.println("after solve again:");
            // System.out.println("keys you have:" + keysYouHave);
            // System.out.println("chests status:" + chests);
            // System.out.println("Result path:" + resultPath);
            // }
            ArrayList<String> tmp1 = (ArrayList<String>) resultPath.clone();
            sortByLengthAsc(tmp1);
            String statusKey1 = tmp1.toString();
            // System.out.println("key1:" + statusKey);
            if (isSolved) {
                Status.put(statusKey1, true);
                return true;
            }
            if (!isSolved) {
                // reset
                chest.isOpen = false;
                chestIsOpenedNumber--;
                keyInPackage[Integer.valueOf(chest.entryKey)]++;
                keysYouHave += chest.containKeys.size();// you have more keys
                for (int j = 0; j < chest.containKeys.size(); j++) {
                    keyInPackage[Integer.valueOf(chest.containKeys.get(j))]--;
                }
                keysYouHave -= chest.containKeys.size();
                keysYouHave++;

                Status.put(statusKey1, false);

                resultPath.remove(chestIndex);
                // System.out.println("Fail and Reset:" + chest);
                // System.out.println("keys you have:" + keysYouHave);
                // System.out.println("chests status:" + chests);
                // System.out.println("Result path:" + resultPath);
            }
        }

        if (haveBeenAllOpened(chests)) {
            return true;
        }
        return false;
    }

    public static boolean haveBeenAllOpened(ArrayList<Chest> list) {
        // if (list.size() == chestIsOpenedNumber) {
        // return true;
        // }
        // return false;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).isOpen == false) {
                return false;
            }
        }
        return true;
    }

    public static boolean isImpossible() {
        for (int i = 0; i < 401; i++) {
            if (keyConsumers[i] > allSupplyKeys[i]) {
                return false;
            }
        }
        return true;
    }

    public static void sortByLengthAsc(ArrayList<String> squarelist) {
        Comparator comp = new MyComparator();
        Collections.sort(squarelist, comp);
    }

}
